package org.lintcode_Close.Stage1_Easy_50.O6简单递归;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-21:55
 * @Description:
 * @version: 1.0
 */
public class BinaryTreeInorderTraversal {

	static class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	// 返回中序遍历的结果
	public List<Integer> inorderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		inorder(root, result);
		return result;
	}

	// 递归实现中序遍历
	private void inorder(TreeNode node, List<Integer> result) {
		if (node == null) {
			return;
		}
		// 递归遍历左子树
		inorder(node.left, result);
		// 访问根节点
		result.add(node.val);
		// 递归遍历右子树
		inorder(node.right, result);
	}

	public static void main(String[] args) {
		// 构建一个示例二叉树
		//       1
		//      / \
		//     2   3
		//    / \
		//   4   5
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.left.left = new TreeNode(4);
		root.left.right = new TreeNode(5);

		BinaryTreeInorderTraversal traversal = new BinaryTreeInorderTraversal();
		List<Integer> result = traversal.inorderTraversal(root);
		System.out.println(result); // 输出应为 [4, 2, 5, 1, 3]
	}
}
